{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Sensitivity: Algebraic explanation\n", "## Changes in the coefficients of the objective function" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us start with the Production Mix Problem example, which in the standard form is:\n", "\n", "$max Z = 300x_{1} + 250x_{2} + 0s_{1} + 0s_{2} + 0s_{3}$\n", "\n", "subject to:\n", "\n", "$2x_{1} + x_{2} + s_{1} = 40$ \n", "$x_{1} + 3x_{2} + s_{2} = 45$ \n", "$x_{1} + s_{3} = 12$ \n", "\n", "The final Tableau is:\n", "\n", "| Basic | z | $x_{1}$ | $x_{2}$ | $s_{1}$ | $s_{2}$ | $s_{3}$ | RHS | Ratio |\n", "|---------|---|---------|---------|---------|---------|---------|------|-------|\n", "| - | 1 | 0 | 0 | 0 | 250/3 | 650/3 | 6350 | - |\n", "| $s_{1}$ | 0 | 0 | 0 | 1 | -1/3 | -5/3 | 5 | - |\n", "| $x_{2}$ | 0 | 0 | 1 | 0 | 1/3 | -1/3 | 11 | - |\n", "| $x_{1}$ | 0 | 1 | 0 | 0 | 0 | 1 | 12 | - |\n", "\n", "Let us assume we want to make a change in coefficient $c_{1}$ of $\\Delta c_{1}$. The objective function becomes:\n", "\n", "$max Z = (300 +\\Delta c_{1})·x_{1} + 250x_{2}$\n", "\n", "It can be proved that the final Tableau now becomes:\n", "\n", "| Basic | z | $x_{1}$ | $x_{2}$ | $s_{1}$ | $s_{2}$ | $s_{3}$ | RHS | Ratio |\n", "|---------|---|-----------------|---------|---------|---------|---------|------|-------|\n", "| - | 1 | $-\\Delta c_{1}$ | 0 | 0 | 250/3 | 650/3 | 6350 | - |\n", "| $s_{1}$ | 0 | 0 | 0 | 1 | -1/3 | -5/3 | 5 | - |\n", "| $x_{2}$ | 0 | 0 | 1 | 0 | 1/3 | -1/3 | 11 | - |\n", "| $x_{1}$ | 0 | 1 | 0 | 0 | 0 | 1 | 12 | - |\n", "\n", "The Simplex method requires that the Tableau is in canonical form. Thus, we need to add the last row times $\\Delta c_{1}$ to the first row to fulfill this:\n", "\n", "| Basic | z | $x_{1}$ | $x_{2}$ | $s_{1}$ | $s_{2}$ | $s_{3}$ | RHS | Ratio |\n", "|---------|---|---------|---------|---------|---------|------------------------|--------------------------|-------|\n", "| - | 1 | 0 | 0 | 0 | 250/3 | 650/3 + $\\Delta c_{1}$ | 6350 + 12·$\\Delta c_{1}$ | - |\n", "| $s_{1}$ | 0 | 0 | 0 | 1 | -1/3 | -5/3 | 5 | - |\n", "| $x_{2}$ | 0 | 0 | 1 | 0 | 1/3 | -1/3 | 11 | - |\n", "| $x_{1}$ | 0 | 1 | 0 | 0 | 0 | 1 | 12 | - |" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And taking into account that the coefficient of $s_{3}$ needs to be positive for $x_{1}$ to remain in the basis, $\\Delta c_{1}$ cannot be lower than -650/3 and can increase up to infinity." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Let us now assume we want to make a change in coefficient $c_{2}$ of $\\Delta c_{2}$. The objective function becomes:\n", "\n", "$max Z = 300·x_{1} + (250 +\\Delta c_{2})·x_{2}$\n", "\n", "The final Tableau now becomes:\n", "\n", "| Basic | z | $x_{1}$ | $x_{2}$ | $s_{1}$ | $s_{2}$ | $s_{3}$ | RHS | Ratio |\n", "|---------|---|---------|-----------------|---------|---------|---------|------|-------|\n", "| - | 1 | 0 | $-\\Delta c_{2}$ | 0 | 250/3 | 650/3 | 6350 | - |\n", "| $s_{1}$ | 0 | 0 | 0 | 1 | -1/3 | -5/3 | 5 | - |\n", "| $x_{2}$ | 0 | 0 | 1 | 0 | 1/3 | -1/3 | 11 | - |\n", "| $x_{1}$ | 0 | 1 | 0 | 0 | 0 | 1 | 12 | - |\n", "\n", "Again, the Simplex method requires that the Tableau is in canonical form. Thus, we need to add the second last row times $\\Delta c_{2}$ to the first row to fulfill this:\n", "\n", "| Basic | z | $x_{1}$ | $x_{2}$ | $s_{1}$ | $s_{2}$ | $s_{3}$ | RHS | Ratio |\n", "|---------|---|---------|---------|---------|--------------------------|--------------------------|--------------------------|-------|\n", "| - | 1 | 0 | 0 | 0 | 250/3 + $\\Delta c_{2}/3$ | 650/3 - $\\Delta c_{2}/3$ | 6350 + 11·$\\Delta c_{2}$ | - |\n", "| $s_{1}$ | 0 | 0 | 0 | 1 | -1/3 | -5/3 | 5 | - |\n", "| $x_{2}$ | 0 | 0 | 1 | 0 | 1/3 | -1/3 | 11 | - |\n", "| $x_{1}$ | 0 | 1 | 0 | 0 | 0 | 1 | 12 | - |" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "And taking into account that the coefficients of $s_{2}$ and $s_{3}$ need to be positive for $x_{2}$ to remain in the basis, $\\Delta c_{2}$ cannot be lower than -250 nor higher than 650." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Changes in the constraint independent terms" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now let us see what is the effect of changing b, for instance decreasing $b_{1}$ an amount equal to $\\Delta b_{1}$. In the original problem formulation, this means: \n", "\n", "$2x_{1} + x_{2} + s_{1} = 40 - \\Delta b_{1}$\n", "\n", "$x_{1} + 3x_{2} + s_{2} = 45$ \n", "\n", "$x_{1} + s_{3} = 12$" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Changing the Right Hand Side by $\\Delta b_{1}$ is equivalent to changing $s_{1}$ an amount of $\\Delta b_{1}$. Note that $s_{1}$ is in the basis, thus for it to remain in the basis, it must satisfy: \n", "\n", "$s_{1}=5 + \\Delta b_{1} \\geq 0$\n", "\n", "$\\Delta b_{1} \\geq -5$\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "Now, take the second constraint and let us apply the same change:\n", "\n", "$2x_{1} + x_{2} + s_{1} = 40$\n", "\n", "$x_{1} + 3x_{2} + s_{2} = 45 - \\Delta b_{2}$\n", "\n", "$x_{1} + s_{3} = 12$\n", "\n", "Again, this is equivalent to: \n", "\n", "$2x_{1} + x_{2} + s_{1} = 40$\n", "\n", "$x_{1} + 3x_{2} + s_{2} + \\Delta b_{2} = 45$\n", "\n", "$x_{1} + s_{3} = 12$ \n", "\n", "Which can be regarded as a change of $\\Delta b_{2}$ in $s_{2}$. Now, if we change $s_{2}$ from $s_{2}=0$ to $s_{2} =\\Delta b_{2}$ in the final Tableau:\n", "\n", "| Basic | z | $x_{1}$ | $x_{2}$ | $s_{1}$ | $s_{2}$ | $s_{3}$ | RHS | Ratio |\n", "|---------|---|---------|---------|---------|-----------------------|---------|------|-------|\n", "| - | 1 | 0 | 0 | 0 | 250/3·$\\Delta b_{2}$ | 650/3 | 6350 | - |\n", "| $s_{1}$ | 0 | 0 | 0 | 1 | -1/3 ·$\\Delta b_{2}$ | -5/3 | 5 | - |\n", "| $x_{2}$ | 0 | 0 | 1 | 0 | 1/3 ·$\\Delta b_{2}$ | -1/3 | 11 | - |\n", "| $x_{1}$ | 0 | 1 | 0 | 0 | 0 ·$\\Delta b_{2}$ | 1 | 12 | - |\n", "\n", "The basis remains unchanged as long as all the constraints are still met:\n", "\n", "$s_{1} - 1/3 · \\Delta b_{2} = 5$\n", "\n", "$x_{2} + 1/3· \\Delta b_{2} = 11$\n", "\n", "$x_{1} + 0 ·\\Delta b_{2} = 12$ \n", "\n", "$s_{1} = 5 + 1/3 · \\Delta b_{2} \\geq 0 (\\Delta b_{2} \\geq -15)$ \n", "$x_{2} = 11 - 1/3· \\Delta b_{2} \\geq 0 (\\Delta b_{2} \\leq 33)$ \n", "$x_{1} = 12 - 0·\\Delta b_{2} \\geq 0 (\\Delta b_{2} \\leq Inf)$" ] } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.7.4" }, "pycharm": { "stem_cell": { "cell_type": "raw", "source": [], "metadata": { "collapsed": false } } } }, "nbformat": 4, "nbformat_minor": 2 }